/*
   Summary:
   This implementation is similar to the Segregated Free List Algorithm. The memory
   manager keeps track of all the free blocks of memory in the heap and keeps them in
   segregated free lists.

   Block Structure:
   Each Block of free memory is at least 16 bytes big. It has the following 4 fields:
    - HEADER, containing size and a bit to indicate whether the block is allocated
    - A pointer to the next free block in the list
    - A pointer to the previous free block in the list
    - Optional free space, in multiples of 4 bytes
    - A footer, that is identical to the header

   Free Lists:
   There are 128 doubly linked free lists that the free blocks go into. Bins 0-64 hold
   blocks of exact sizes (from 16 bytes to 512 bytes). Bins 65-127 hold blocks of a
   range of sizes. The small bins are sorted as a FIFO where as the larger bins are
   sorted in size order.

 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

#include "mm.h"
#include "memlib.h"

/*********************************************************
 * NOTE TO STUDENTS: Before you do anything else, please
 * provide your team information in the following struct.
 ********************************************************/
team_t team = {
    /* Team name */
    "HanSolo",
    /* First member's full name */
    "Hani Abdo",
    /* First member's email address */
    "hani.abdo@utoronto.ca",
    /* Second member's full name (leave blank if none) */
    "Mustafa Abbas",
    /* Second member's email address (leave blank if none) */
    "mustafa.abbas@utoronto.ca"
};

/*************************************************************************
 * Basic Constants and Macros
 * You are not required to use these macros but may find them helpful.
*************************************************************************/
#define WSIZE       4            /* word size (bytes) */
#define DSIZE       8            /* doubleword size (bytes) */
#define CHUNKSIZE   (1<<14)      /* initial heap size (bytes) */
#define OVERHEAD    8            /* overhead of header and footer (bytes) */

#define MAX(x,y) ((x) > (y)?(x) :(y))

/* Pack a size and allocated bit into a word */
#define PACK(size, alloc) ((size) | (alloc))

/* Read and write a word at address p */
#define GET(p)          (*(size_t *)(p))
#define PUT(p,val)      (*(size_t *)(p) = (val))

/* Read the size and allocated fields from address p */
#define GET_SIZE(p)     (GET(p) & ~0x7)
#define GET_ALLOC(p)    (GET(p) & 0x1)

/* Given block ptr bp, compute address of its header and footer */
#define HDRP(bp)        ((char *)(bp) - WSIZE)
#define FTRP(bp)        ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
#define PRVP(bp)        ((char *)(bp) + WSIZE)

/* Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8
#define ALIGNMENT_MASK (ALIGNMENT-1)

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)

#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

/* defining bins and indexing macros */
#define NUM_BINS 128
// if the size is less than 512 bytes
#define MAX_SMALL_SIZE 512

#define MIN_SIZE 16

// index conversion macros
#define SMALL_BIN_INDEX( sz ) \
    ( ((unsigned long)(sz)) >> 3 )

#define BIN_INDEX(sz)                                                     \
    ((((unsigned long)(sz) >> 9) ==    0) ?       ((unsigned long)(sz) >>  3):\
     (((unsigned long)(sz) >> 9) <=    4) ?  56 + ((unsigned long)(sz) >>  6):\
     (((unsigned long)(sz) >> 9) <=   20) ?  91 + ((unsigned long)(sz) >>  9):\
     (((unsigned long)(sz) >> 9) <=   84) ? 110 + ((unsigned long)(sz) >> 12):\
     (((unsigned long)(sz) >> 9) <=  340) ? 119 + ((unsigned long)(sz) >> 15):\
     (((unsigned long)(sz) >> 9) <= 1364) ? 124 + ((unsigned long)(sz) >> 18):\
     126)

void * heap_listp = NULL;

//define bins as size with pointer to first block
typedef struct
{
    void * first;
    void * last;
} bin; 

typedef bin * binPtr;

//head of bin list
binPtr head = NULL;

// wilderness and recently split indices
#define WILDERNESS 0
#define RECENTLY_SPLIT 1

#define wilderness_bp ( head[WILDERNESS] )
#define recently_split_bp ( head[RECENTLY_SPLIT] )

//function headers
void binEmptyBlock(void * bp);
void *extend_heap(size_t words);
void split_block(void* bp, size_t index, size_t asize);

/**********************************************************
 * mm_init
 * Initialize the heap, including "allocation" of the
 * bins and the wilderness block
 **********************************************************/
 int mm_init(void) {
     //allocate enough space for NUM_BINS bins
     if ((heap_listp = mem_sbrk(NUM_BINS*sizeof(bin))) == NULL)
         return -1;

     int i;
     //cast heap pointer to bin pointer
     head = (binPtr)heap_listp;
     
     //initialize size and pointers of bins
     for (i=0; i<NUM_BINS; i++) {
         head[i].first = NULL;
         head[i].last = NULL;
     }

     //create the prologue
     if ((heap_listp = mem_sbrk(4*WSIZE)) == NULL)
         return -1;
     PUT(heap_listp, 0); // Alignment Padding
     PUT(heap_listp+WSIZE, PACK(OVERHEAD, 1)); // Prologue Header
     PUT(heap_listp+DSIZE, PACK(OVERHEAD, 1)); // Prologue Footer
     // epilogue header TODO, should the alloc bit be 1? :
     PUT(heap_listp+WSIZE+DSIZE, PACK(0, 1));

     // calling extend_size to allocate an initial wilderness block
     head[WILDERNESS].first = NULL;
     if ((heap_listp = extend_heap(CHUNKSIZE/WSIZE)) == NULL)
         return -1;

     // TODO: don't need this, as extend_heap does this
     //head[WILDERNESS].first = (void *)heap_listp;
     return 0;
 }

//This function is used to check if the heap is consistent
//It iterates through each of the bins and performs following checks:
//    any block in a bin is free
//    first and last pointers of bin are consistent
//    previous pointers are set correctly
//    neighbour blocks are allocated (else we are not coalescing)
int mm_check(void)
{
    int i;
    //iterate through bins
    for(i = 2; i < NUM_BINS; i++)
    {
        //pointer should be consistent
        if (head[i].first == NULL && head[i].last != NULL)
        {
           printf("Bin pointers inconsistent\n");
           return 1;
        }

        //pointer should be consistent
        if (head[i].first != NULL && head[i].last == NULL)
        {
           printf("Bin pointers inconsistent\n");
           return 1;
        }
     

        //get initial pointer to traverse
	void * next = head[i].first;

        //set initial previous pointer to null
	void * prev = NULL;          

        //while bin contains more blocks
	while(next) {
                //coalesced?
                if (!GET_ALLOC(FTRP(PREV_BLKP(next))) || !GET_ALLOC(HDRP(NEXT_BLKP(next))))
                {
                    printf("Coalesce not working\n");
                    return 2;
                }
                
                //verify unallocated
		if (GET_ALLOC(HDRP(next)))
                {
                    printf("Block in bin is allocated\n");
                    return 3;
                }

                //verify previous pointer
                if (GET(PRVP(next)) != prev)
                {
                    printf("Previous pointer not set correctly\n");
                    return 4;
                } 
		prev = next;
		next = GET(next); 
	} 
        
        //verifies bins last pointer points to last block in list
        if (head[i].first != NULL && head[i].last != prev)
        {
            printf("Bin last pointer is not correctly set\n");
	    return 5;
        }
    }
    return 0;
}
 
/* coalescing with the next block
   this function is called by coalesce
 */
void * coalesce_next(void * bp) {
    size_t size = GET_SIZE(HDRP(bp));
    void * next = NEXT_BLKP(bp);
    size_t next_size = GET_SIZE(HDRP(next));
    if (next == head[WILDERNESS].first) {
        //if the block was right next to the wilderness
        //merge the two blocks here
        size += next_size;
        head[WILDERNESS].first = bp;
        //adjust header and footer
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
        return NULL;
    }
    else {
        // just another block
        size += next_size;
        //merge the two blocks here, using place() to unlink
        place(next, next_size);
        //adjust header and footer
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
        return bp;
    }
}

/* coalescing with the previous block
   this function is called by coalesce
 */
void * coalesce_prev(void * bp) {
    size_t size = GET_SIZE(HDRP(bp));
    void * prev = PREV_BLKP(bp);
    size_t prev_size = GET_SIZE(HDRP(prev));
    //merge the two blocks here, use place() unlink it
    place(prev, prev_size);
    size += prev_size;
    //adjust header and footer
    PUT(HDRP(prev), PACK(size, 0));
    PUT(FTRP(prev), PACK(size, 0));
    return prev;
}

/**********************************************************
 * coalesce
 * checks if the neighbours are allocated and uses the
 * helper functions coalesce_prev and coalesce_next to coalesce
 * - also checking and merging with the wilderness block
 **********************************************************/
void *coalesce(void *bp)
{
    //check which of the adjecent blocks are allocated
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    size_t size = GET_SIZE(HDRP(bp));

    if (!prev_alloc)
        //the previous block is free, call the helper function to merge it
        bp = coalesce_prev(bp);

    if (!next_alloc)
        //the next block is free, call the helper function to merge it
        bp = coalesce_next(bp);

    return bp;
}

/**********************************************************
 * extend_heap
 * Extend the heap by "words" words, maintaining alignment
 * requirements of course. Merging the new space with the 
 * wilderness block, if it exists. and changing the header
 **********************************************************/
void *extend_heap(size_t words)
{
    char *bp;
    size_t size;

    /* Allocate an even number of words to maintain alignments */
    size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;

    if ((bp = mem_sbrk(size)) == -1) {
        printf("heap size = %d\n", mem_heapsize());
        return NULL;
    }

    /* Initialize free block header/footer and the epilogue header */
    PUT(HDRP(bp), PACK(size, 0));                // free block header
    PUT(FTRP(bp), PACK(size, 0));                // free block footer
    // TODO: do we need this:
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));        // new epilogue header

    if (head[WILDERNESS].first == NULL) { // no wilderness block was there!
        head[WILDERNESS].first = (void *)bp;
    }
    else { // there was a wilderness block, we merge the new space with it
        // reading the size of the wilderness block and adding it to size
        size += GET_SIZE(HDRP(head[WILDERNESS].first));
        // store the size information in the header and footer
        PUT(HDRP(head[WILDERNESS].first), PACK(size, 0));
        PUT(FTRP(head[WILDERNESS].first), PACK(size, 0));
    }
    return head[WILDERNESS].first;
}


/**********************************************************
 * find_fit
 * Traverse the heap searching for a block to fit asize
 * Return NULL if no free blocks can handle that size
 * Assumed that asize is aligned and adjusted to multiple of 8
 **********************************************************/
void * find_fit(size_t asize) 
{
    size_t binIndex;
    char * bp;
    if (asize < MAX_SMALL_SIZE) { //small sizes
        binIndex = SMALL_BIN_INDEX(asize);
    }
    else { //larger sizes
        binIndex = BIN_INDEX(asize);
    }
 
    for (; binIndex < NUM_BINS; binIndex++)
    {
        //first check if the specified bin is empty or not
        if (head[binIndex].first != NULL) {
            // the list is not empty
            //insert into sorted position within the bin list
            void* next = head[binIndex].first;

            //find correct position
            while(next && GET_SIZE(HDRP(next)) < asize)
            {
                next = GET(next);
            }
            
            //if large enough element wasn't found try larger bin
            if (!next)
               continue;
 
            //split block if it is large enough to be split
            if (GET_SIZE(HDRP(next)) >= asize + 16 )
            {
               split_block(next, binIndex, asize);
            }

            return next;
        }
    }

    return NULL;
}

/**********************************************************
 * split_block
 * takes in a pointer to a block, index to bin it is in, 
 * and size we want to split
 * correctly removes block from its bin, and splits it into
 * two blocks based on size needed and initalizes them
 * adds new blocks to correct bins
 **********************************************************/
void split_block(void* bp, size_t index, size_t asize)
{
    //get size of original block and part we want to split off
    size_t bsize = GET_SIZE(HDRP(bp));
    size_t diff = bsize - asize;

    //initialize header and footer of new block
    PUT(HDRP(bp), PACK(asize, 0));
    PUT(FTRP(bp), PACK(asize, 0));
 
    //set pointer to next block (now the part of original being split off)
    void* end_block = NEXT_BLKP(bp);

    //initialize split off block
    PUT(HDRP(end_block), PACK(diff, 0));
    PUT(FTRP(end_block), PACK(diff, 0));
    
    //remove from current bin, handle pointer fixes
    void* prev = GET(PRVP(bp));
    void* next = GET(bp);

    if (prev)
        PUT(prev, next);
    else if (next)
        head[index].first = next;
    else
        head[index].first = NULL;
    
    if (next)
        PUT(PRVP(next), prev);
    else if (prev)
        head[index].last = prev;
    else
        head[index].last = NULL;

    //put blocks into correct bins
    binEmptyBlock(bp);
    binEmptyBlock(end_block);
} 


/**********************************************************
 * place
 * Mark the block as allocated
 **********************************************************/
void place(void* bp, size_t asize)
{
    /* Get the current block size */
    size_t bsize = GET_SIZE(HDRP(bp));

    size_t binIndex;
    if (bsize < MAX_SMALL_SIZE) { //small sizes
        binIndex = SMALL_BIN_INDEX(bsize);
    }
    else { //larger sizes
        binIndex = BIN_INDEX(bsize);
    }

    //set block as allocated
    PUT(HDRP(bp), PACK(bsize, 1));
    PUT(FTRP(bp), PACK(bsize, 1));
    
    //get next and previous pointers of block
    void* prev = GET(PRVP(bp));
    void* next = GET(bp);

    //adjust pointers of previous block to remove block from list
    if (prev)
        PUT(prev, next);
    else if (next) //was first in list
        head[binIndex].first = next;
    else //was only block in list
        head[binIndex].first = NULL;
    
    if (next) //next exists, fix its pervious pointer
        PUT(PRVP(next), prev);
    else if (prev) //was last block
        head[binIndex].last = prev;
    else //was only block in bin
        head[binIndex].last = NULL;
}

/**********************************************************
 * binEmptyBlock
 * takes an empty block and put it in the correctbin, does 
 * not coalesce though, use coalesce function for that
 **********************************************************/
void binEmptyBlock(void * bp) {
    //find the size, and assume that it is appropriate
    size_t size = GET_SIZE(HDRP(bp));
    int binIndex;

    if (size < MIN_SIZE) {
        binIndex = SMALL_BIN_INDEX(size);
        //inserting the element such that it was the most recently used
        //connecting the node to the top

        if (head[binIndex].first == NULL && head[binIndex].last == NULL) {
            //for empty list
            PUT(bp, NULL);
            PUT(PRVP(bp), NULL);
            head[binIndex].first = bp;
            head[binIndex].last = bp;
        }
        else {
            //for non empty list
            PUT(bp, head[binIndex].first);
            PUT(PRVP(bp), NULL);
            head[binIndex].first = bp;
            PUT(PRVP(GET(bp)), bp);
        }
    }
    else {
        binIndex = BIN_INDEX(size);
        //inserting such that smallest sizes are on the top of the list
        
        if (head[binIndex].first == NULL && head[binIndex].last == NULL) {
            //inserting into an empty list
            PUT(bp, NULL);
            PUT(PRVP(bp), NULL);
            head[binIndex].first = bp;
            head[binIndex].last = bp;
        }
        else {
            //inserting into a non empty list, find the spot to put it in
            //insert into sorted position within the bin list
            void * next = head[binIndex].first;
            void * prev = NULL;          

            //find correct position
            while(next && GET_SIZE(HDRP(next)) < size) {
                prev = next;
                next = GET(next); 
            } // search complete

            // insert bp into position, fix pointers
            PUT(bp, next);
            PUT(PRVP(bp), prev);
            if (prev)
                PUT(prev, bp);
            else
                head[binIndex].first = bp;
            if (next)
                PUT(PRVP(next), bp);
            else
                head[binIndex].last = bp;
        }
    }
}

/**********************************************************
 * mm_free
 * Free the block and coalesce with neighbouring blocks
 **********************************************************/
void mm_free(void *bp)
{
    //testing corner cases
    //if NULL or zero was passed in
    if (bp == 0 || bp == NULL)
        return;
    
    //if the block was already free don't do anything
    if (!(GET_ALLOC(HDRP(bp))))
        return;
    
    //set to unused, modifying the header and the footer
    size_t size = GET_SIZE(HDRP(bp));
    PUT(HDRP(bp), PACK(size,0));
    PUT(FTRP(bp), PACK(size,0));

    //coalesce here
    //bp = coalesce(bp);
    //also check if it is adjecent to the wilderness block

    //bin the free block if it was not merged in with the wilderness
    if (bp != NULL)
        binEmptyBlock(bp);
}

/* To get size of chunk from a requested memory size
 * this basically adds 4 to the size and then rounds it up to the nearest 8
 **********************************************************/
size_t request2size( size_t reqSize )
{
    size_t chunkSize;

    chunkSize = reqSize + WSIZE + ALIGNMENT_MASK;

    if ( chunkSize < (MIN_SIZE + ALIGNMENT_MASK) ) {
        chunkSize = MIN_SIZE;
    } else {
        chunkSize &= ~ALIGNMENT_MASK;
    }
    return chunkSize;
}

/**********************************************************
 * mm_malloc
 * Allocate a block of size bytes.
 * The type of search is determined by find_fit
 * The decision of splitting the block, or not is determined
 * in place(..)
 * If no block satisfies the request, the heap is extended
 **********************************************************/
void *mm_malloc(size_t size)
{
    size_t asize; /* adjusted block size */
    size_t extendsize; /* amount to extend heap if no fit */
    char * bp;
    
    /* Ignore spurious requests, TODO: may change later */
    if (size <= 0)
        return NULL;

    /* Adjust block size to include overhead and alignment reqs. */
    asize = request2size(size);

    /* Search the bins for a fit, this is done by calling find_fit */
    if ((bp = find_fit(asize)) != NULL) {
        place(bp, asize);
        return bp;
    }

    //find_fit returned NULL, use the wilderness block
    char * wildernessBp = head[WILDERNESS].first;
    if (wildernessBp == NULL) {
        //no free block available, call extend heap as is
        extendsize = MAX(asize, CHUNKSIZE);
        if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
            return NULL;
    }
    else {
        // some free space is there, if not enough, then allocate more
        size_t sizeOfWilderness = GET_SIZE(HDRP(wildernessBp));
        if (sizeOfWilderness < asize) {
            extendsize = MAX(asize-sizeOfWilderness, CHUNKSIZE);
            if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
                return NULL;
        }
    }

    //the wilderness has been increased, now lets split it
    //and then place it, and then return!

    size_t diff = GET_SIZE(HDRP(head[WILDERNESS].first)) - asize;
    bp = head[WILDERNESS].first;

    //changin the bp fields
    if (diff >= 16) {
        //split the wilderness block
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));
        
        //new wilderness pointer
        head[WILDERNESS].first = NEXT_BLKP(bp);
        PUT(HDRP(head[WILDERNESS].first),PACK(diff,0));
        PUT(FTRP(head[WILDERNESS].first),PACK(diff,0));
    }
    else {
        //allocate the whole thing and set wilderness to NULL
        //reading the size again
        asize = GET_SIZE(HDRP(bp));
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));
        
        head[WILDERNESS].first = NULL;
    }

    return bp;
}

/**********************************************************
 * mm_realloc
 * Implemented simply in terms of mm_malloc and mm_free
 *********************************************************/
void *mm_realloc(void *ptr, size_t size)
{
    //if null is passed in, just act like malloc
    if (ptr == NULL) {
        return mm_malloc(size);
    }

    void *oldptr = ptr;
    void *newptr;
    size_t copySize;
    
    //call malloc to get new space
    newptr = mm_malloc(size);
    if (newptr == NULL)
      return NULL;

    //copy the contents of the old space over
    copySize = GET_SIZE(HDRP(oldptr));
    if (size < copySize)
      copySize = size;
    memcpy(newptr, oldptr, copySize);
    //free the old stuff
    mm_free(oldptr);
    return newptr;
}

